package cn.edu.njust.alg.leetcode;

import java.util.Arrays;

/**
 * 创建时间：2015年6月15日 上午11:47:37 项目名称：AlgorithmExercise
 * 
 * @author Zhou Xiumin
 * @version 1.0
 * @since JDK 1.7.0_21 文件名称：Leetcode_0_t.java 类说明：
 */
public class Leetcode_105_Construct_Binary_Tree_from_Preorder_and_Inorder_Traversal {

	public static TreeNode buildTree(int[] preorder, int[] inorder) {
		if (preorder.length == 0 || inorder.length == 0) {
			return null;
		}
		int i;
		TreeNode root = new TreeNode(preorder[0]);
		for (i = 0; i < inorder.length; i++) {
			if (inorder[i] == preorder[0]) {
				break;
			}
		}
		int[] il = Arrays.copyOfRange(inorder, 0, i);
		int[] ir = Arrays.copyOfRange(inorder, i + 1, inorder.length);
		int lenl = il.length;
		int[] pl = Arrays.copyOfRange(preorder, 1, lenl + 1);
		int[] pr = Arrays.copyOfRange(preorder, lenl + 1, preorder.length);
		root.left = buildTree(pl, il);
		root.right = buildTree(pr, ir);
		return root;
	}

	private static void pretravel(TreeNode root) {
		if (root == null) {
			return;
		}
		System.out.print(root.val + " ");
		pretravel(root.left);
		pretravel(root.right);
	}

	private static void intravel(TreeNode root) {
		if (root == null) {
			return;
		}
		pretravel(root.left);
		System.out.print(root.val + " ");
		pretravel(root.right);
	}

	private static void potravel(TreeNode root) {
		if (root == null) {
			return;
		}
		pretravel(root.left);
		pretravel(root.right);
		System.out.print(root.val + " ");
	}

	public static void main(String[] args) {
		/*
		 * 先序：ABCDEGF 1234576
		 * 
		 * 中序：CBEGDFA 3257461
		 * 
		 * 后序：CGEFDBA 3756421
		 */
		int[] pr = { 1, 2, 3, 4, 5, 7, 6 };
		int[] in = { 3, 2, 5, 7, 4, 6, 1 };
		//int[] po = { 3, 7, 5, 6, 4, 2, 1 };
		TreeNode root = buildTree(pr, in);
		pretravel(root);
		System.out.println();
		intravel(root);
		System.out.println();
		potravel(root);
		System.out.println();

	}

}
